This invention relates generally to improvements in digital versatile disc (DVD) systems and, more particularly, to playback of disc content by such systems. The invention may find application in a variety of other multimedia applications.
a) Digital Versatile Disc Systems
Digital versatile discs (DVDs) are information storage devices used for storing prerecorded audio information, video and other visual information, and computer software. The storage mechanism used in DVDs closely resembles that used in compact discs (CDs). DVD players also use the same laser technology as CD players. Briefly, both DVDs and CDs store information as a pattern of pits formed in a metallic substrate. The pit patterns form digital words and can be read by shining a laser beam on the disc surface and detecting the reflected beam. The information storage capacity of a typical DVD, however, is much higher than a CD. Presently available DVDs have a variety of capacities which depend on the technology used to manufacture the discs. Single-layer technologies can be either single or double-sided with current capacities of 4.7 gigabytes and 9.4 gigabytes, respectively. Dual layer technologies use single or double sided technologies that currently hold approximately 8.5 gigabytes per side.
DVDs can store information in several formats. DVD-VIDEO discs can store video information (e.g., movies, TV episodes, or music videos) using known information compression algorithms, such as MPEG-2 for video compression/decompression. DVD-ROM discs can store digital data in compressed form for computer use, though the format is usually significantly different from that found on DVD-VIDEO discs.
DVD-VIDEO players are often directed to the consumer market for entertainment use in homes, e.g., for high-resolution, high-fidelity playback of movies or music. DVD-VIDEO players have many CD player features, such as the ability to play selections in any order desired and the ability to read information from any point on the disc. Therefore, DVDs are finding a significant market as a preferred storage and playback system for a wide variety of multimedia.
Information concerning DVD-VIDEO content, discs and players, including (without limitation) data encoding/decoding, data formatting and structures, and navigation and playback, can be had with reference to the xe2x80x9cDVD 1.0 Specification for Read-Only Discxe2x80x9d, Vol. 3 (herein referred to as the xe2x80x9cDVD Specificationxe2x80x9d). The DVD Specification can be obtained, for example, from Toshiba Corp., 1-1 Shibaura 1-Chome, Minato-ku, Tokyo 105-01 Japan.
The data on a DVD-VIDEO disc is organized into a hierarchical set of disc (or physical) data structures, and a corresponding, hierarchical set of presentation (or logical) data structures. The disc data structures contain DVD-VIDEO data arranged in a way closely linked to the physical location and arrangement of the data on the DVD-VIDEO discs. On the other hand, presentation data structures are independent of the physical order of the data on the disc and serve a role of providing navigational information that determines the presentation order of the DVD content. With this versatile arrangement, a DVD-VIDEO disc can contain multiple titles, and/or alternative playback sequences within a title, with the disc""s data shared among its different titles and playback sequences.
The multiple types or layers of presentation data structures are given below:
Disc Data Structures
Video Title Set (VTS)
Video Object Sets (VOBSs)
Video Objects (VOBs)
Cell Objects (cells)
Title is both a memory data structure and logical construct constituting a creative work stored on a DVD-VIDEO disc, such as an individual movie. A DVD-VIDEO title can contain up to 999 program chain objects (PGCs). PGCs can be used to create different versions (camera angles, ratings, outcomes, etc.) of the same title. Each PGC of a DVD-VIDEO links between zero and 99 related program objects, and governs the order in which its programs are to be played. A simple DVD-VIDEO title can contain only one PGC; however, complex titles can contain two or more PGCs to allow user access to and control of a variety of programs (i.e., interactive user control). A multiple-PGCs title can play programs sequentially, randomly (with program repeats), or in shuffle mode (without program repeats). Each program object, for example, a scene of a movie, is an ordered collection of pointers to cells. Individual cells may be used in more than one PGC, different PGCs defining different, alternative sequences through the DVD content. Additionally, a DVD-VIDEO title can have multiple Parts_of_Title (PTTs), each referencing a program object. PTTs are analogous to chapters of a book, and, e.g., can mark different scenes of a movie. PTTs divide a DVD-VIDEO title into a maximum of 99 different parts. Individual PTTs can be part of the same or different PGCs.
The multiple types or layers of presentation data structures are given below:
Presentation Data Structures
Title
PTT""(s)
Program Chain (PGC)
Program(s) (PGs)
Cells (pointers)
A video title set (VTS) is essentially analogous to a title and takes the form, on the disc, of a main directory called a VIDEO_TS directory. The VIDEO_TS directory references two types of files distinguished with the file extensions, .IFO and .VOB. A file with the .VOB extension consists of the VOBS data structure, which contains the actual multimedia data in a number of cells. A file with the .IFO extension contain navigational data structures and a processor-independent interpreted language that specifies how the VOBS data structures are arranged and where the associated data are located on the disc. During playback, a DVD-VIDEO player sorts the files on the disc to form a number of video title sets, for example, a number of movies. Each VTS is a grouping of all files on the disc necessary to play a particular title, and is composed of one .IFO file and one or more associated .VOB files containing pointers to a number of individual cells.
The disc structures and presentation structures are linked at the cell level. Each cell specifies, for example, all the video and audio data associated with a group of pictures in the VTS and may span multiple disc blocks. Essentially, a cell constitutes the smallest addressable chunk of data on the DVD-VIDEO disc. A cell is divided into VOBUs, each of which being a container object that includes both multimedia data and playback program commands in an interleaved format. VOBUs, in turn, are broken into packs of packets of compressed bits of video and audio data. Different packs contain data for specifying navigating order (NAV-PCKs) and subpictures, in addition to video (V-PCK) and audio (A-PCK). Each packet on a DVD-VIDEO disc consists of 2048 bytes from a single bitstream, aligned to a disc block.
While a VOBU is playing, the DVD-VIDEO player can obtain input directly from a user by means of controls, such as buttons, which can be displayed under playback program control onscreen along with the multimedia data. For example, user selection of a button can cause the playback program to jump to a new location on the disk and begin playback at the new location. Some DVD content is specifically designed for user-interactive operation, where users can actually change the flow of a video or movie, or change its ending, by user input specifying a different, particular PGC of the title. Such interactive operation results in a change in the order of playback of the individual cells forming the title.
b) Cell Starting and Running Times
DVD-VIDEO players have the responsibility for monitoring starting times of cells. This information can be used to provide users, in real-time during playback, with the length of time expired during playback of the title. Unfortunately, the DVD discs cannot store a starting time for playback of each cell. Cells on a DVD-VIDEO disc are played at different times in the presentation of a single title on the disc pursuant to different PGCs, or at different times in the presentation of different titles on the disc. Therefore, there is no known, reliable way to pre-determine and store cell starting times on pre-recorded discs.
For this reason, known DVD-VIDEO systems determine cell starting times before a title plays by walking through the title""s data structures, monitoring and storing the playback length for each cell, and then calculating the starting times for a given cell by adding the playback lengths of previous cell(s). For example, a title could have a Cell A of length 10 milliseconds, Cell B of 50 milliseconds and Cell C of 30 milliseconds, etc. If these cells were played back sequentially, Cells A, B and C would have respective playback starting times of zero, ten and sixty milliseconds. These starting times are typically stored in a cache memory. Cache memory is used in DVD systems to perform read-ahead operations in order to minimize the time required to retrieve data and in order to handle interrupts that halt the transfer of data from a disc to the playback system. Unfortunately, the size of memory in current DVD-VIDEO players usually precludes use of this approach to store cell starting times.
This can be better understood from the following description of such DVD-VIDEO memory requirements. A title can contain up to ninety-nine chapters (PTTs). Each PTT references a DVD program within a PGC. Each PGC can contain up to 255 cells. Typically, a starting time is stored in a four-byte field, specifying the time typically in milliseconds in a binary coded decimal form. Under a worse case scenario, where a title contains 99 PTTs, and each PGC is unique and contains 255 cells, the total memory consumption for the title can be calculated as follows:
99 PTTsxc3x971 PGCxc3x97255 cells per PGCxc3x974 bytes per cell=100,980 bytes
It can thus be seen that storing the starting times for all possible combinations of cells can result in a relatively high memory requirement of over 100 kilobytes.
This approach of storing all the cell starting times in memory can be suitable for use in a DVD drive of a computer system, which has large amounts of the computer""s virtual memory available. Unfortunately, it is often not suitable for memory-constrained environments, which cannot store such quantities of data. Current, stand-alone DVD-VIDEO players intended for the consumer market typically incorporate non-expandable cache memories of only 32 or 64 kilobytes due to cost constraints. Such cache memories are too small to store all the approx. 100 kilobytes of data for the worse case scenario described above.
Another approach to calculation of cell starting times entails, at each cell boundary, reloading all preceding cells and calculating time expired before the current cell. Unfortunately, this approach has a negative performance implication since, typically, content playback would cease, the DVD drive would seek to different locations on the disc and intensive calculations would need to take place before playback could resume.
Accordingly, it would be desirable to provide a system for monitoring starting times of cells, which utilizes available memory efficiently and is suitable for use in consumer-oriented DVD-VIDEO players. Such a system should be able to determine also, in real time, the running time expired during playback of the title, e.g., for display to users.
The invention resides in maintaining in memory the following data structures used for determining cell starting times, e.g., for DVD titles: a snapshot of starting times for the xe2x80x9cmost likelyxe2x80x9d to be played cells, and a list of xe2x80x9chintsxe2x80x9d so that starting times for cells outside this most likely list can be quickly determined.
The xe2x80x9cmost likelyxe2x80x9d to be played cells are preferably those of an active program chain (PGC) cells outside the most likely list are, preferably, those of other PGCs of a title, if any). An xe2x80x9cactivexe2x80x9d program chain is the program chain currently being played at any particular time. The hints list can be provided by a chapter or PTT array which contains starting times of only those chapters of the active PGC. The snapshot in memory of starting times of most likely to be played cells can be provided by a cell array that contains cell starting times for only those cells of the active PGC. The stored information is sufficient to determine current running time of a title. There is no need to store starting times for PTTs or cells of non-active program chains. A DVD-VIDEO player can use the stored information to determine the starting time of the current cell, track current running time of a title, and display such running time for users, e.g., on a DVD-VIDEO display.
A preferred embodiment uses these arrays in tandem to determine the starting times for an active cell of a DVD-VIDEO title. The cell array""s starting times are sufficient to provide all cell starting times for single-PGC titles (i.e., individual titles having a single PGC). Both the cell array""s and PTT array""s starting times are used to calculate cell starting times for multi-PGC titles (i.e., individual titles having two or more PGCs). During playback, the starting time stored in the cell array for a starting cell of a PGC is set to the value stored in the PTT array for the starting time of a starting PTT of the PGC. The starting times stored in the cell array for each subsequent cell of the PGC is computed by adding the PGC""s prior cells"" lengths to the starting cell""s starting time. With this approach, the starting time for the active cell is always in memory. If a new PGC is to be played, the starting times for the cells in the new PGC are computed, and only the starting times of those cells need be stored in the cell array. Maintaining the hints list makes calculation of these cell times for a new PGC a simple matter.
More particularly, in the preferred embodiment, a processor in the DVD player walks though each PTT encountered in a DVD-VIDEO bitstream supplied by a DVD-VIDEO source, loads the program and PGC specifier referenced by that PTT into the memory, and computes the starting times for all the cells in that PTT. The starting times of all cells of PTTs referencing the same PGC are loaded in the cell array. Since the majority of the PTTs exist in the same PGC, the data in the cell array can satisfy requests for starting times of cells of the active PGC, whether it is the sole PGC of a single-PGC title or one PGC of a multi-PGC title. For multi-PGC titles, when a new PGC (e.g., the second, third, etc., up to the last PGC of the title) is encountered in the bitstream and the starting time for a cell is requested, the cell array is refreshed (i.e., re-loaded) with the cell starting times for that new PGC. These are obtained by determining the starting time of the starting PTT of the new PGC by adding the duration of the last cell of the prior PGC to that cell""s starting time, and storing the result in the PTT array entry for the starting PTT of the new PGC. Then, the processor uses the starting time of the starting PTT of the new PGC, as stored in the PTT array, as the starting time of the starting cell of the PGC. The processor walks through each PTT of the new PGC, and each of the cells of each of those PTTs, calculating their starting times and storing them in the respective PTT array and cell array. Their respective starting times can be calculated by adding the durations of prior cells/PTTs in the new PGC to the starting time of that starting cell. This embodiment repeats these steps for each PGC of the title. Thus, the cell array contains the starting times of only cells of the active PGC, and the PTT array contains the starting times of only PTTs of the active PGC.
The foregoing-described implementation permits cell playback timing information to be efficiently stored in memory. It can be stored in as little as four bytes of memory for each PTT in the active PGC, plus four bytes for each cell in the active PGC. Advantageously, in the preferred embodiment, a starting time for the currently playing cell can be resident and available in cache memory at all times during playback. The memory can accommodate even the worse case scenario described above for a title having the maximum number of PTTs, PGCs and cells permitted by the DVD Specification. Moreover, for most titles, once the most likely cell starting times are calculated (i.e., the starting times of cells of the active PGC), it is unlikely these times will have to be swapped out by starting time for other cells since PGCs that require such changes are unusual. If swapping occurs, only the starting times for the cells in a new PGC need to be recalculated.